package Hot_100;

import org.junit.Test;

/*  62. 不同路径
    一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
    问总共有多少条不同的路径？


    解题思路：这是一道简单的迷宫问题
        1)使用dfs进行试探；如果不采用记忆性搜索，会出现大量子问题重复求解导致超时
        2)dp:
*/
public class T62_uniquePaths {

//    --------------------------DFS---------------------------------------
    public int uniquePaths_1(int m, int n) {
        int[][] memo = new int[m][n];   //记忆集，记录到达该格可以走的路径数
        return DFS(m, n, 0, 0, memo);
    }

    int DFS(int m, int n, int x, int y,int[][]memo) {
        if (x < 0 || x >= m || y < 0 || y >= n) {   //越界
            return 0;
        }

        if (memo[x][y] != 0) {  //相同子问题，直接返回结果
            return memo[x][y];
        }

        if (x == m - 1 && y == n - 1) { //到达出口
            return 1;
        }

        int count=0;
        count += DFS(m, n, x + 1, y,memo);       //向下
        count += DFS(m, n, x, y + 1, memo);       //向右

        memo[x][y] = count; //记录子问题的求解结果

        return count;
    }
//    -----------------------------------------------------------------

//    ------------------------dp-----------------------------------------
    public int uniquePaths_2(int m, int n) {
        int dp[][] = new int[m][n];

//        左边界和上边界全为1
        for (int i = 0; i < m; i++) {   //左边界
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {   //上边界
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //简单的递推式
            }
        }
        return dp[m-1][n-1];
    }




    @Test
    public void test() {
//        System.out.println(uniquePaths_1(3, 7));
        System.out.println(uniquePaths_2(3, 7));
    }
}

/*
    未优化前代码
class Solution {
    int count=0; //记录可到达的路径条数

    public int uniquePaths(int m, int n) {
        int[][] mg = new int[m][n];
        DFS(mg, m, n, 0, 0);
        return count;
    }

    void DFS(int[][] mg, int m, int n, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n) {   //越界处理
            return;
        }

        if (x == m - 1 && y == n - 1) { //到达出口
            count++;
            return;
        }

        DFS(mg, m, n, x + 1, y);    //向下
        DFS(mg, m, n, x, y + 1);    //向右
    }
}
* */